//
// Created by francklinson on 2021/11/28 AT 14:28.
// May Saint Diana bless you!
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.size() < p.size())
            return vector<int>{};
        // 先统计目标中的各个字母
        vector<int> target(26, 0);
        for (const char &x: p) {
            ++target[x - 'a'];
        }
        // 统计s中最开始的一段
        vector<int> cur(26, 0);
        for (int i = 0; i < p.size(); ++i) {
            ++cur[s[i] - 'a'];
        }
        vector<int> ans;
        if (cur == target)
            ans.push_back(0);
        // 遍历左端点
        for (int i = 0; i < s.size() - p.size(); ++i) {
            // 移动区间
            --cur[s[i] - 'a'];
            ++cur[s[i + p.size()] - 'a'];
            // 判断满足条件的
            if (cur == target) {
                ans.push_back(i + 1);
            }
        }
        return ans;
    }
};

int main() {
    Solution solution;
    vector<int> ans = solution.findAnagrams("abab", "ab");
    for (const int &x: ans) cout << x << endl;
    return 0;
}

